翻訳と辞書 Words near each other ・ Lefteris Vogiatzes ・ Lefteris Zagoritis ・ Leftfield ・ Leftfield (disambiguation) ・ Leftfoot ・ Lefties ・ Lefties Soul Connection ・ Leftism (album) ・ Leftist Alliance ・ Leftist errors (Yugoslavia) ・ Leftist guerrilla groups of Iran ・ Leftist Socialist Party of Japan ・ Leftist tree ・ LeftLion ・ Leftover Cuties ・ Leftover hash lemma ・ Leftover Salmon ・ Leftover Wine ・ Leftovers ・ Leftoverture ・ LeftRightLeftRightLeft ・ Leftside ・ Leftvent ・ Leftwich ・ Leftwich (disambiguation) ・ Leftwich (surname) ・ Leftwich House ・ Leftwich Trophy ・ Leftwing Movement ・ Leftwing Revolutionary Nationalist Movement Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Leftover hash lemma ： ウィキペディア英語版 Leftover hash lemma The leftover hash lemma is a lemma in cryptography first stated by Russell Impagliazzo, Leonid Levin, and Michael Luby. Imagine that you have a secret key $\backslash scriptstyle\; X$ that has $\backslash scriptstyle\; n$ uniform random bits, and you would like to use this secret key to encrypt a message. Unfortunately, you were a bit careless with the key, and know that an adversary was able to learn about bits of that key, but you do not know which. Can you still use your key, or do you have to throw it away and choose a new key? The leftover hash lemma tells us that we can produce a key of about $\backslash scriptstyle\; n\; \backslash ,-\backslash ,\; t$ bits, over which the adversary has almost no knowledge. Since the adversary knows all but $\backslash scriptstyle\; n\; \backslash ,-\backslash ,\; t$ bits, this is almost optimal. More precisely, the leftover hash lemma tells us that we can extract a length asymptotic to $\backslash scriptstyle\; H\_\backslash infty(X)$ (the min-entropy of $\backslash scriptstyle\; X$) bits from a random variable $\backslash scriptstyle\; X$ that are almost uniformly distributed. In other words, an adversary who has some partial knowledge about $\backslash scriptstyle\; X$, will have almost no knowledge about the extracted value. That is why this is also called privacy amplification (see privacy amplification section in the article Quantum key distribution). Randomness extractors achieve the same result, but use (normally) less randomness. Let $\backslash scriptstyle\; X$ be a random variable over $\backslash scriptstyle\; \backslash mathcal\; X$ and let $\backslash scriptstyle\; m\; \backslash ;>\backslash ;\; 0$. Let $\backslash scriptstyle\; h\; :\backslash ;\; \backslash mathcal\; \backslash ,\backslash times\backslash ,\; \backslash mathcal\; \backslash ;\backslash rightarrow\backslash ;\; \backslash ^m$ be a 2-universal hash function. If :$m\; \backslash leq\; H\_\backslash infty(X)\; -\; 2\; \backslash log\backslash left(\backslash frac\backslash right)$ then for $\backslash scriptstyle\; S$ uniform over $\backslash scriptstyle\; \backslash mathcal\; S$ and independent of $\backslash scriptstyle\; X$, we have :$\backslash delta(X),\; S),\; (U,\; S))\; \backslash leq\; \backslash varepsilon$ where $\backslash scriptstyle\; U$ is uniform over $\backslash scriptstyle\; \backslash ^m$ and independent of $\backslash scriptstyle\; S$. $\backslash scriptstyle\; H\_\backslash infty(X)\; \backslash ;=\backslash ;\; -\backslash log\; \backslash max\_x\; \backslash Pr()$ is the Min-entropy of $\backslash scriptstyle\; X$, which measures the amount of randomness $\backslash scriptstyle\; X$ has. The min-entropy is always less than or equal to the Shannon entropy. Note that $\backslash scriptstyle\; \backslash max\_x\; \backslash Pr()$ is the probability of correctly guessing $\backslash scriptstyle\; X$. (The best guess is to guess the most probable value.) Therefore, the min-entropy measures how difficult it is to guess $\backslash scriptstyle\; X$. $\backslash scriptstyle\; \backslash delta(X,\backslash ,\; Y)\; \backslash ;=\backslash ;\; \backslash frac\; \backslash sum\_v\; \backslash left\; |\; \backslash Pr()\; \backslash ,-\backslash ,\; \backslash Pr()\; \backslash right\; |$ is a statistical distance between $\backslash scriptstyle\; X$ and $\backslash scriptstyle\; Y$. ==See also== * Universal hashing * Min-entropy * Rényi entropy * Information theoretic security 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Leftover hash lemma」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.